package microsfot.java;

import java.util.Stack;

/**
 *	   10
   6       14
4    8   12   16

4=6=8=10=12=14=16
  其实就是一个二叉树的先序遍历
 *
 *exp1
 *      10 
 *4 6 8    12 14 16
 *
 *4 6 8 10 12 14 16
 */

public class ReverseDoubleLinkList {
	BNode buildTree(){
		BNode root=new BNode(10);
		BNode n6=new BNode(6);
		BNode n14=new BNode(14);
		BNode n4=new BNode(4);
		BNode n8=new BNode(8);
		
		BNode n12=new BNode(12);
		BNode n16=new BNode(16);
		
		root.left=n6;
		root.right=n14;
		
		n6.left=n4;
		n6.right=n8;
		
		n14.left=n12;
		n14.right=n16;
		return root;
	}
	Stack<BNode> nodeStack=new Stack<BNode>();
	void change2LinkList(BNode root){
		if(root!=null){
			change2LinkList(root.left);
			nodeStack.push(root);
			change2LinkList(root.right);
		}
	}
	
	void reverse(){
		while(!nodeStack.isEmpty() && nodeStack.size()>2){
			BNode right=nodeStack.pop();
			BNode root=nodeStack.pop();
			BNode left=nodeStack.pop();
			
			root.left=left;
			root.right=right;
			
			right.left=root;
			left.right=root;
			
			nodeStack.push(left);
		}
	}
	
	public void display(){
		BNode first=nodeStack.peek();
		BNode last=null;
		while(first!=null){
			last=first;
			System.out.print(first+"===>");
			first=first.right;
		}
		
		System.out.println("From right to left");
		while(last!=null){
			System.out.print(last+"<=====");
			last=last.left;
		}
		
	}
	
	
	/**
	 * second change to double click list 
	 */
	BNode reverse2(BNode root){
		if(root==null){
			return null;
		}
		
		if(root.left!=null){
			BNode left=reverse2(root.left);
			while(left.right!=null){
				left=left.right;
			}
			
			root.left=left;
			left.right=root;
		}
		
		if(root.right!=null){
			BNode right=reverse2(root.right);
			while(right.left!=null){
				right=right.left;
			}
			root.right=right;
			right.left=root;
		}
		
		return root;
	}
	
	BNode change2List(BNode root){
		if(root==null){
			return null;
		}
		root=reverse2(root);
		while(root.left!=null){
			root=root.left;
		}
		return root;
	}
	
	void display2(BNode root){
		while(root!=null){
			root=root.right;
		}
	}
	public static void main(String[] args) {
		ReverseDoubleLinkList list=new ReverseDoubleLinkList();
		BNode root=list.buildTree();
		list.change2LinkList(root);
		System.out.println(list.nodeStack);
		System.out.println("After reverse");
		list.reverse();
		System.out.println(list.nodeStack);
		
		list.display();
	}
	
}


class BNode{
	public Integer data;
	public BNode left;
	public BNode right;
	
	public BNode(Integer data){
		this.data=data;
	}
	
	public String toString(){
		return data+"";
	}
}